package algo;

import java.util.Arrays;

/**
 * Created by pc on 2015/1/18.
 * 从右往左
 * 外层是n次循环，内层是小于n-j-1
 * 比较的次数是 n*(n-1)/2，当完全逆序时交换的次数和比较的次数一样*
 * 只要是2层循环嵌套基本上可断定是O(N的平方)*
 */
public class BubbleSort {
    public static void sort(int[] toSortArr) {
        int temp;
        boolean sorted;

        //外面一层从后往前数，里面一层限制最右边的点则跟j扯上关系
        for (int j = 0; j < toSortArr.length; j++) {
            //假定这一趟不用再排了，已经排好了
            sorted = true;
            for (int i = 0; i < toSortArr.length - j - 1; i++) {
                if (toSortArr[i] > toSortArr[i + 1]) {
                    temp = toSortArr[i + 1];
                    toSortArr[i + 1] = toSortArr[i];
                    toSortArr[i] = temp;
                    //还是发生了交换
                    sorted = false;
                }
            }
            //没有发生交换就不用再排了，效率高一点
            System.out.println("\t" + (j +1) + ", " + Arrays.toString(toSortArr));
            if (sorted) break;
        }
    }

    public static void main(String args[]) {
        int[] myArr = new int[]{4, 23, 52, 34, 29};
//        int[] myArr = RandomArray.getRandomIntArray(10);
        System.out.println("before sort:" + Arrays.toString(myArr));
        BubbleSort.sort(myArr);
        System.out.println("after sort:" + Arrays.toString(myArr));

    }
}
